File compression technology has recently experienced a resurgence. Originally, file compression was necessary because disk space was limited. To maximize the number of files that could be stored on a disk, it was occasionally necessary to compress files. More recently, hard disk space has become very cheap, and users have been able to store massive quantities of data. The need for compression to save disk space has diminished.
At the same time that disk space has become cheap, however, another bottleneck has arisen: throughput. Although people enjoy the freedom the Internet gives them, in terms of research and file transfer, most people use limited throughput connections to the Internet. For example, at 56 Kbps, to transfer a 1 MB file takes approximately 2 minutes and 26 seconds. A single image file, storing a 1024×768 image in true color, taking up 2.25 MB of space, requires 5 and a half minutes to download. Multiply that time by several files, and the transfer times become a serious problem.
One technique used to reduce the size of the file is to limit the number of colors used in the image. There are two reasons why including a large number of colors in an image is impractical or unnecessary. First, the computer hardware on which the image is displayed (i.e., the monitor and video card) might be limited in the number of colors that can be displayed at one time. Second, the human eye is limited in the number of colors it can distinguish when looking at an image. To address these concerns, a typical image uses a color palette, which includes either a subset of the colors in the image or approximations of the colors in the image. The number of entries in the color palette determines the number of different colors that occur in the image. In the preferred embodiment of the invention, the color palette of the image includes 256 colors, but a person skilled in the art will recognize that this number can vary. The Median Cut or a similar algorithm can be used to select the colors stored in the color palette. The specifics of how the colors are selected for the color palette is not relevant to the invention and will not be discussed here.
Using a color palette begins the process of compressing the image. For example, if the image is stored using 24-bit color, it takes three bytes to store the color for each pixel. If only 256 colors are used and stored in the color palette, the color for each pixel can be represented using only one byte: the index into the color palette. This reduces the size of the image file by two thirds.
Further compression is also possible. For example, instead of using one byte to identify the index into the color palette for a pixel, a Huffman coding can be applied to the indices into the color palette for the pixels. In a Huffman coding, the frequencies for each symbol (in this case, the different colors in the color palette) in the message (in this case, the image) are calculated. The entire image is scanned, and the number of times each color is counted is scanned. The frequency for each color can then be determined by dividing the number of occurrences of each color by the total number of pixels in the image.
Once the frequencies of each symbol in the message are known, a Huffman tree can be constructed. FIG. 10 shows the construction of the Huffman tree. In FIG. 10, there are four symbols, “A,” “B,” “C,” and “D,” with the respective frequencies of 0.10, 0.20, 0.30, and 0.40. The frequencies start out as leaves 1005, 1010, 1015, and 1020 in a to-be-constructed tree. The two smallest frequencies are assigned a common parent node in the tree, and the parent node is assigned a frequency equal to the sum of its children. In FIG. 10, the two smallest frequencies are 0.10 and 0.20, which combine to a parent node frequency of 0.30. The process then repeats, using the parent node's frequency in place of its two children, until only a single (root) node remains.
Once the Huffman tree is constructed, the two children of each parent node are assigned a “0” or a “1”, depending on whether they are a “left” or a “right” branch from the parent node. (A person skilled in the art will recognize that the determination of which branch is “left” and which is “right” is arbitrary.) The Huffman coding for each symbol is the sequence of branches from the root node of the Huffman tree to the leaf for that symbol. For example, the Huffman coding for symbol “D” is “1”, whereas the Huffman coding for symbol “B” is “001.”
The advantage of Huffman coding is that symbols that occur frequently are assigned shorter codes than symbols that occur infrequently. As can be seen from the example of FIG. 10, the symbol “D” occurs 40% of the time in the message, whereas symbol “B” occurs only 20% of the time. Because there are more occurrences of the symbol “D,” a shorter code for the symbol “D” as compared with symbol “B” will result in a shorter message.
There are two problems with using a Huffman coding as described above. First, the image must be scanned twice: once to determine the Huffman codes, and once to compress the image. Huffman coding cannot be determined while scanning the image. Second, because the coding is necessary to determine the appropriate color for each pixel, the coding must be stored in the compressed image file.
Other techniques exist to compress images: for example JPEG (Joint Photographic Expert Group) and MPEG (Motion Picture Expert Group) compression. These techniques allow for fast compression and decompression. But JPEG and MPEG compression techniques are lossy: that is, they achieve high fast compression rates by losing information. Typically, the loss is imperceptible: for example, with still images compressed using JPEG compression, the lost information is typically below the level of perception of the human eye. But often, the user cannot afford to lose information from the image that needs to be compressed. For such images, JPEG and MPEG compression is useless.
Accordingly, a need remains for a way to compress digital images that addresses these and other problems associated with the prior art.
Appendix A shows an implementation of the compression algorithm described herein, implemented in the C programming language and including comments.